`
https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
  const nodes = []

  const traverse = (root, row, col) => {
    if (root === null) return

    // 记录每个结点
    nodes.push(new Node(root, row, col))

    traverse(root.left, row + 1, col - 1)
    traverse(root.right, row + 1, col + 1)
  }

  // 遍历所有结点，记录所有结点对应的行和列
  traverse(root, 0, 0)

  // 根据题目要求进行排序
  nodes.sort((a, b) => {
    // 行和列都相同就按值大小排序
    if (a.row === b.row && a.col === b.col) return a.node.val - b.node.val
    // 列相同就按行大小排序
    if (a.col === b.col) return a.row - b.row
    // 否则用列大小排序
    return a.col - b.col
  })

  const res = []

  // 记录上一列的编号
  let lastCol = -Infinity
  for (let i = 0; i < nodes.length; i++) {
    const cur = nodes[i]
    if (cur.col !== lastCol) {
      // 开始记录新的一列
      res.push([])
      lastCol = cur.col
    }
    res[res.length - 1].push(cur.node.val)
  }

  return res
};

class Node {
  constructor(node, row, col) {
    this.node = node
    this.row = row
    this.col = col
  }
}